import org.junit.Test;

import java.util.*;

public class Solution {
    /**
     * 给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
     *
     * 更正式地，检查是否存在两个下标 i 和 j 满足：
     *
     * i != j
     * 0 <= i, j < arr.length
     * arr[i] == 2 * arr[j]
     */
    @Test
    public void checkIfExist(){
//        int[] arr = new int[]{10,2,5,3};
        int[] arr = new int[]{3,1,7,11};
        System.out.println(checkIfExist(arr));
    }

    public boolean checkIfExist(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i : arr) {
            if(i % 2 == 0 ) {
                if (map.containsKey(i / 2) || map.containsKey(i * 2)) {
                    return true;
                }
            }
            else if(map.containsKey(i * 2)){
                return true;
            }
            map.put(i,1);
        }
        return false;
    }

    /**
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     */
    @Test
    public void invertTree(){
        int[] arr = new int[]{4,2,7,1,3,6,9};
        int mark = 0;
        for (int i : arr) {

            mark++;
        }
        invertTree(null);
    }

    public TreeNode invertTree(TreeNode root) {

        if(root == null){
            return null;
        }
        //获取右节点
        TreeNode right = root.right;
        invertTree(right);

        //获取左节点
        TreeNode left = root.left;
        invertTree(left);

        root.left = right;
        root.right = left;

        return root;
    }

    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }


    /**
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     */
    @Test
    public void findAnagrams() {
        String s = "cbaebabacd";
        String p = "abc";

        for (Integer anagram : findAnagrams(s, p)) {
            System.out.print(anagram + ",");
        }
    }


    public List<Integer> findAnagrams(String s, String p) {
        List<Integer>  result = new ArrayList<>();
        Map<Integer,Integer> smap = new HashMap<>();
        Map<Integer,Integer> pmap = new HashMap<>();


        for (int i = 0; i < 26; i++) {
            smap.put(i,0);
            pmap.put(i,0);
        }

        for (int i = 0; i < p.length(); i++) {
            int integer = p.charAt(i) - 'a';
            pmap.put(integer, pmap.get(integer) + 1);
        }

        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            int integer = s.charAt(i) - 'a' ;
            smap.put(integer,smap.get(integer) + 1);
            if(i < p.length()-1) continue;
            if(smap.equals(pmap)){
                result.add(left);
            }
            smap.put(s.charAt(left)-'a',smap.get(s.charAt(left)-'a') -1);
            left++;
        }
        return result;
    }

    /**
     *给定一个二叉树的根节点 root ，返回它的 中序 遍历。
     */
    @Test
    public void inorderTraversal(){
        inorderTraversal(null);
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        if(root != null){
            //先遍历左节点
            list.addAll(inorderTraversal(root.left));
            //自身
            list.add(root.val);
            //遍历右节点
            list.addAll(inorderTraversal(root.right));
        }

        return list;
    }


    /**
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     *
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     */
    @Test
    public void isSameTree(){

    }

    public boolean isSameTree(TreeNode p, TreeNode q) {

        if((p == null && q != null) || (p != null && q == null)){
            return false;
        }
        if(p == null && q == null){
            return true;
        }

        if(p.val != q.val){
            return false;
        }

        else if(!isSameTree(p.left,q.left)){
            return false;
        }
        else if(!isSameTree(p.right,q.right)){
            return false;
        }

        return true;
    }
}
